package com.gorkr.backtracking;

import org.junit.jupiter.api.Test;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @author gorkr
 * @date 2022/06/21 17:01
 **/
public class M17LetterCombinationsOfAPhoneNumber {

     private HashMap<Character, char[]> map = new HashMap<>();
    private List<String> res = new ArrayList<>();




    public List<String> letterCombinations(String digits) {
        if(Objects.equals(digits, "")){
            return res;
        }

        map.put('2', new char[]{'a', 'b', 'c'});
        map.put('3', new char[]{'d','e','f'});
        map.put('4', new char[]{'g','h','i'});
        map.put('5', new char[]{'j','k','l'});
        map.put('6', new char[]{'m', 'n', 'o'});
        map.put('7', new char[]{'p','q','r','s'});
        map.put('8', new char[]{'t','u','v'});
        map.put('9', new char[]{'w','x','y','z'});
        char[] digitsChars = digits.toCharArray();
        LinkedList<Character> outStr = new LinkedList<>();
        backTracking(outStr,digitsChars,0 );
        return res;

    }
    private void backTracking(LinkedList<Character> outStr, char[] digitsChars , int index){

        // base case
        if(index==digitsChars.length){
            StringBuilder sb = new StringBuilder();
            for (Character c :
                    outStr) {
                sb.append(c);
            }
            res.add(sb.toString());
            return;
        }

        char[] chars = map.get(digitsChars[index]);



        for (char aChar : chars) {
            // 做选择
            outStr.add(aChar);
            index++;
            backTracking(outStr, digitsChars, index);
            // 撤销选择
            outStr.removeLast();
            index--;
        }

    }

    @Test
    public void test(){
        System.out.println(letterCombinations(""));
    }

}
    